import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


public class Text {
    public static void main(String[] args) {
        HashMap<Character,Integer> set =new HashMap<>();
        String s ="123";
        Character ch =s.charAt(1);
        System.out.println();
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o1.getValue();
            }
        });
        ArrayList<Integer> list =new ArrayList<>();
        LinkedHashSet<Integer> set1 =new LinkedHashSet<>();
        set1.size();
        List<Integer> list1 =new ArrayList<>();
        list1.add(1);
        list1.add(1);
        list1.add(1);
        //list1.sort(((o1, o2) -> o1.));
        Integer[] tmp =(Integer[]) list1.toArray();
        List<List<Integer>> list2 =new ArrayList<>();

    }



    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i=0;
        int j=0;
        int count =0;
        int[] newArray =new int[m+n];
        while(i<m && j<n){
            if(nums1[i]<=nums2[j]){
                newArray[count++] =nums1[i++];
            }else{
                newArray[count++]=nums2[j++];
            }
        }

        while(i<m){
            newArray[count++] =nums1[i++];
        }
        while(j<n){
            newArray[count++]=nums2[j++];
        }
        System.arraycopy(newArray,0,nums1,0,m+n);

    }


    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2,0,nums1,m,n);
        Arrays.sort(nums1);
    }



    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<m;i++){
            list.add(nums1[i]);
        }
        for(int i=0;i<n;i++){
            list.add(nums2[i]);
        }
        list.sort((o1,o2)->o1.compareTo(o2));
        for (int i=0;i<n+m;i++){
            nums1[i]=list.get(i);
        }
    }

    public void merge3(int[] nums1, int m, int[] nums2, int n) {
        int i=m-1;
        int j =n-1;
        int k=m+n-1;
        while(i>=0 && j>=0){
            if(nums1[i]>=nums2[j]){
                nums1[k--] =nums1[i--];
            }else{
                nums1[k--]=nums2[j--];
            }
        }
        while(i>=0){
            nums1[k--] =nums1[i--];
        }
        while(j>=0){
            nums1[k--]=nums2[j--];
        }
    }



    public int removeDuplicates1(int[] nums) {
        int count =0;
        int tmp =nums[0];
        for(int i=0;i<nums.length;i++){
            if(tmp!=nums[i]){
                nums[count]=tmp;
                tmp=nums[i];
                count++;
            }
        }
        nums[count]=tmp;
        return count+1;
    }

    public int removeDuplicates2(int[] nums) {
        LinkedHashSet<Integer> set =new LinkedHashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        int count =0;
        for(Integer ret:set){
            nums[count] =ret;
            count++;
        }
        return count;
    }


    public int removeElement2(int[] nums, int val) {
        int count =0;
        for(int i =0;i<nums.length;i++){
            if(nums[i]!=val){
                nums[count]=nums[i];
                count++;
            }
        }
        return count;
    }

    public int removeElement1(int[] nums, int val) {
        int slow =0;
        for(int fast =0;fast<nums.length;fast++){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }


    public int removeElement(int[] nums, int val) {
        ArrayList<Integer> list =new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=val){
                list.add(nums[i]);
            }
        }
        for(int i=0;i<list.size();i++){
            nums[i] =list.get(i);
        }
        return list.size();
    }


    public List<String> topKFrequent1(String[] words, int k) {
        // 统计词频
        Map<String, Integer> frequencyMap = new HashMap<>();
        for (String word : words) {
            frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);
        }

        // 创建最小堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(
                (entry1, entry2) -> entry1.getValue().equals(entry2.getValue()) ?
                        entry2.getKey().compareTo(entry1.getKey()) :
                        entry1.getValue() - entry2.getValue()
        );

        // 维护大小为k的堆
        for (Map.Entry<String, Integer> entry : frequencyMap.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // 构建结果（需要反转）
        List<String> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll().getKey());
        }
        Collections.reverse(result);

        return result;
    }

    public List<String> topKFrequent2(String[] words, int k) {
        HashMap<String,Integer> map =new HashMap<>();
        for(String s :words){
            if(!map.containsKey(s)){
                map.put(s,1);
            }else{
                Integer value = map.get(s);
                map.put(s,value+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> queue =
                new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
                    public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
                        if(o1.getValue().equals(o2.getValue())){
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
        int count =0;
        for(Map.Entry<String,Integer> entry :map.entrySet()){
            if(count!=k){
                queue.offer(entry);
                count++;
            }else{
                Map.Entry<String,Integer> ret =queue.peek();
                if(entry.getValue().equals(ret.getValue())){
                    if(entry.getKey().compareTo(ret.getKey())<0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }else{
                    if(entry.getValue().compareTo(ret.getValue())>0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }
            }
        }
        ArrayList<String> list =new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }


    /**
     * 方法1
     * @param args
     */
    public static void findBadKeyboard1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine().toUpperCase();
            String b = in.nextLine().toUpperCase();
            HashSet<Character> set =new HashSet<>();
            for(int i=0;i<b.length();i++){
                set.add(b.charAt(i));
            }
            HashSet<Character> hashSet =new HashSet<>();
            for(int i=0;i<a.length();i++){
                char c=a.charAt(i);
                if(!set.contains(c)){
                    if(!hashSet.contains(c)){
                        System.out.print(c);
                    }
                    hashSet.add(c);
                }
            }
        }
    }

    /**
     * 方法2
     * @param args
     */
    public static void findBadKeyboard2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine().toUpperCase();
            String b = in.nextLine().toUpperCase();
            boolean[] s1 = new boolean[128];
            boolean[] s2 = new boolean[128];
            for(int i=0;i<b.length();i++){
                char c= b.charAt(i);
                s1[c]=true;
            }
            for(int i=0;i<a.length();i++){
                char c= a.charAt(i);
                if(s1[c]!=true&&s2[c]!=true){
                    System.out.print(c);
                    s2[c]=true;
                }
            }
        }
    }

    /**
     * 方法3
     * @param args
     */
    public static void findBadKeyboard3(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine().toUpperCase();
            String b = in.nextLine().toUpperCase();
            LinkedHashSet<Character> set =new LinkedHashSet<>();
            for(int i=0;i<a.length();i++){
                char c=a.charAt(i);
                set.add(c);
            }
            for(int i=0;i<b.length();i++){
                char c=b.charAt(i);
                if(set.contains(c)){
                    set.remove(c);
                }
            }
            //利用forEacch方法
            //set.forEach(str->System.out.print(str));
            //利用iterable迭代器
            for(char c:set){
                System.out.print(c);
            }
        }
    }

    /**
     * 方法1
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones1(String jewels, String stones) {
        HashSet<Character> set =new HashSet<>();
        for(int i=0;i<jewels.length();i++){
            Character ch =jewels.charAt(i);
            set.add(ch);
        }
        int count =0;
        for(int i=0;i<stones.length();i++){
            Character ch =stones.charAt(i);
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    /**
     * 方法2
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones2(String jewels, String stones) {
        boolean[] s =new boolean[128];
        for(Character c :jewels.toCharArray()){
            s[c] =true;
        }
        int count =0;
        for(Character c :stones.toCharArray()){
            if(s[c]==true){
                count++;
            }
        }
        return count;
    }

    /**
     * 方法3
     * @param jewels
     * @param stones
     * @return
     */
    public int numJewelsInStones3(String jewels, String stones) {
        int count =0;
        for(Character c :stones.toCharArray()){
            if(jewels.indexOf(c)!=-1){
                count++;
            }
        }
        return count;
    }
    /**
     * 方法1
     * 随机链表的复制 利用 HashMap
     * @param head
     * @return
     */
    public Node copyRandomList1(Node head) {
        Node cur =head;
        HashMap<Node,Node> map =new HashMap<>();
        while(cur !=null){
            Node newNode =new Node(cur.val);
            map.put(cur,newNode);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            map.get(cur).next =map.get(cur.next);
            map.get(cur).random =map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }


    /**
     * 方法2 利用递归
     * @param head
     * @return
     */
    HashMap<Node,Node> map =new HashMap<>();
    public Node copyRandomList2(Node head) {
        if(head==null){
            return null;
        }
        if(map.containsKey(head)){
            return map.get(head);
        }
        Node newNode =new Node(head.val);
        map.put(head,newNode);
        newNode.next=copyRandomList2(head.next);
        newNode.random =copyRandomList2(head.random);
        return newNode;
    }

    /**
     * 方法3  暴力解法
     * @param head
     * @return
     */
    public Node copyRandomList3(Node head) {
        if(head==null){
            return head;
        }
        Node cur =head;
        while(cur !=null){
            Node copyNode = new Node(cur.val);
            copyNode.next =cur.next;
            cur.next=copyNode;
            cur=cur.next.next;
        }
        cur =head;
        while(cur!=null){
            if(cur.random!=null){
                cur.next.random=cur.random.next;
            }
            cur=cur.next.next;
        }
        cur=head;
        Node copyHead= head.next;
        Node copycur =copyHead;
        while(cur!=null){
            cur.next=cur.next.next;
            if(copycur.next!=null){
                copycur.next=copycur.next.next;
            }
            copycur=copycur.next;
            cur=cur.next;
        }
        return copyHead;
    }


}

